package ahu.zdw.com;

/**
 * Author: Zhang Dongwei
 * Date: 2021/12/26 20:32
 * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
 * 链表也不会，参考了答案
 *
 */
public class _21_MergeTwoLists {
    public static void main(String[] args) {
        ListNode node = new _21_MergeTwoLists().new ListNode(1);
        System.out.println(node.val);
        ListNode node1 = new _21_MergeTwoLists().new ListNode(3);
        System.out.println(node1.val);
        ListNode node3 = new _21_MergeTwoLists().mergeTwoLists(node1,node);
        while (node3.next!=null) {
            System.out.println(node3.val);
            node3 = node3.next;
        }
    }

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    public class ListNode{
        int val;
        ListNode next;
        ListNode(){}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;

        ListNode head = null;
        if (l1.val <= l2.val){
            head = l1;
            head.next = mergeTwoLists(l1.next, l2);
        } else {
            head = l2;
            head.next = mergeTwoLists(l1, l2.next);
        }
        return head;
    }
}
